COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 4.4
C00003 00003	%folio 397 galley 1 (C) Addison-Wesley 1978	*
C00017 00004	%folio 403 galley 2 (C) Addison-Wesley 1978	*
C00033 00005	%folio 407 galley 3 (C) Addison-Wesley 1978	*
C00052 00006	%folio 411 galley 4a (C) Addison-Wesley 1978	*
C00057 00007	\vfill\eject
C00058 ENDMK
C⊗;
\input acphdr % Section 4.4
\runninglefthead{ARITHMETIC} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{SECTION 4.4 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1978 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{RADIX CONVERSION}
\section{4.4}
\eject
\setcount0 299
%folio 397 galley 1 (C) Addison-Wesley 1978	*
\sectionbegin{4.4. RADIX CONVERSION}
I{\:cF OUR ANCESTORS} had invented arithmetic by counting with
their two fists or their eight fingers, instead of their ten
``digits,'' we would never have to worry about writing binary-decimal
conversion routines.\xskip (And we would perhaps never have learned
as much about number systems.)\xskip In this section, we shall discuss
the conversion of numbers from positional notation with one
radix into positional notation with another radix; this process
is, of course, most important on binary computers when converting
decimal input data into binary form, and converting binary answers
into decimal form.

\subsectionbegin{A. The four basic methods} Binary-decimal
conversion is one of the most machine-dependent operations of
all, since engineers keep inventing different ways to provide
for it in the computer hardware. Therefore we shall discuss
only the general principles involved, from which a programmer
can select the procedure most well suited to his machine.

 We shall assume that only nonnegative numbers enter
into the conversion, since the manipulation of signs is easily
accounted for.

 Let us assume that we are converting from radix
$b$ to radix $B$.\xskip (The methods can also be generalized to mixed-radix
notations, as shown in exercises 1 and 2.)\xskip
Most radix-conversion routines
are based on multiplication and division, using one of the following
four schemes:

\yyskip
1) Conversion of integers (radix point at the right).

\yyskip
\noindent$\bullet$ Method (1a) {\sl Division by $B$} (using
radix-$b$ arithmetic).\xskip Given an integer number $u$, we obtain
its radix-$B$ representation $(U↓M \ldotsm U↓1U↓0)↓B$ as follows:
$$\baselineskip14pt
\eqalign{U↓0 ⊗= u \mod B\cr
U↓1 ⊗= \lfloor u/B\rfloor \mod B\cr
U↓2 ⊗= \lfloor \lfloor u/B\rfloor /B\rfloor \mod B\cr
\ldots\cr}$$
etc., stopping when $\lfloor \ldotsm \lfloor \lfloor
u/B\rfloor /B\rfloor \ldotsm /B\rfloor =0$.

\yyskip
\noindent$\bullet$ Method (1b) {\sl Multiplication by\/\ $b$} (using
radix-$B$ arithmetic).\xskip If $u$ has the radix-$b$ representation
$(u↓m \ldotsm u↓1u↓0)↓b$, we can use radix-$B$ arithmetic to
evaluate the polynomial $u↓mb↑m + \cdots + u↓1b + u↓0=u$ in
the form
$$\biglp (\ldotsm (u↓{m\,}b + u↓{m-1})\,b+\cdotss)\,b+u↓1\bigrp \,b+u↓0.$$

2) Conversion of fractions (radix
point at the left).\xskip Note that it is often impossible to express
a terminating radix-$b$ fraction $(0.u↓{-1}u↓{-2} \ldotsm u↓{-m})↓b$
{\sl exactly} as a terminating radix-$B$ fraction $(0.U↓{-1}U↓{-2}
\ldotsm U↓{-M})↓B$. For example, the fraction ${1\over 10}$ has
the infinite binary representation $(0.0 0011 0011 0011 . . .)↓2$.
Therefore methods of rounding the result to $M$ places are sometimes
of interest.

\yyskip\noindent$\bullet$ Method (2a) {\sl Multiplication by $B$} (using
radix-$b$ arithmetic).\xskip Given a
fractional number $u$, we obtain successive digits of its radix-$B$
representation
$(.U↓{-1}U↓{-2}\ldotsm)↓B$ as follows:
$$\baselineskip14pt
\eqalign{U↓{-1} ⊗= \lfloor uB\rfloor \cr
U↓{-2} ⊗= \lfloor \{uB\} B\rfloor \cr
U↓{-3} ⊗= \lfloor \{\{uB\}B\} B\rfloor \cr
\ldots\cr}$$
where $\{x\}$ denotes $x \mod 1 = x - \lfloor
x\rfloor $. If it is desired to round the result to $M$ places,
the computation can be stopped after $U↓{-M}$ has been calculated,
and $U↓{-M}$ should be increased by unity if $\{\ldotsm\{\{nB\}B\}\ldotsm
B\}$ is greater than ${1\over 2}$.\xskip (Note, however,
that this may cause carries to propagate, and these carries must
be incorporated into the answer using radix-$B$ arithmetic.
It would be simpler to add the constant ${1\over 2}B↑{-M}$
to the original number $u$ before the calculation begins, but
this may lead to a terribly incorrect answer when ${1\over 2}B↑{-M}$
cannot be represented exactly as a radix-$b$ number inside the
computer. Note further that it is possible for the answer to
round up to $(1.00 \ldotsm 0)↓B$, if $b↑m ≥ 2B↑M$.)

Exercise 3 shows how to extend this method so that $M$ is {\sl variable},
just large enough to represent the original number to a specified
accuracy; in this case the problem of carries does not occur.

\yyskip\noindent$\bullet$ Method (2b) {\sl Division by $b$} (using
radix-$B$ arithmetic).\xskip If $u$ has the radix-$b$ representation
$(0.u↓{-1}u↓{-2} \ldotsm u↓{-m})↓b$, we can use radix-$B$ arithmetic
to evaluate $u↓{-1}b↑{-1} + u↓{-2}b↑{-2} + \cdots + u↓{-m}b↑{-m}$
in the form
$$\biglp(\ldotsm (u↓{-m}/b + u↓{1-m})/b + \cdots
+ u↓{-2})/b + u↓{-1}\bigrp /b.$$
Care should be taken to control errors
that might occur due to truncation or rounding in the division
by $b$; these are often negligible, but not always.

\yyskip
To summarize, Methods (1a), (1b), (2a), and (2b)
give us two choices for a conversion process, depending on whether
our number is an integer or a fraction. And it is certainly
possible to convert between integers and fractions by multiplying
or dividing by an appropriate power of $b$ or $B$; therefore
there are at least four methods to choose from when trying to
do a conversion.

\subsectionbegin{B. Single-precision conversion}
To illustrate these four methods, let us assume that \MIX\ is
a binary computer, and suppose that we want to convert a binary
integer $u$ to a decimal integer. Thus $b = 2$ and $B =
10$. Method (1a) could be programmed as follows:
$$\vcenter{\mixthree{\!
⊗ENT1⊗0⊗Set $j ← 0$.\cr
⊗LDX⊗U\cr
⊗ENTA⊗0⊗Set $\rAX ← u$.\cr
1H⊗DIV⊗=10=⊗$(\rA, \rX) ← (\lfloor \rAX/10\rfloor , \rAX \mod 10)$.\cr
⊗STX⊗ANSWER,1⊗$U↓j ←\rX$.\cr
⊗INC1⊗1⊗$j ← j + 1$.\cr
⊗SRAX⊗5⊗$\rAX ← \rA$.\cr
⊗JXP⊗1B⊗Repeat until result is zero.\quad\blackslug\cr}}\eqno (1)$$
This requires $18M + 4$ cycles to obtain $M$ digits.

The above method uses division by 10; Method (2a)
uses {\sl multiplication} by 10, so it might be a little faster.
In order to use Method (2a), we must deal with fractions, and
this leads to an interesting situation. Let $w$ be the word
size of the computer, and assume that $u < 10↑n < w$. With a
single division we can find $q$ and $r$, where
$$wu=10↑nq + r,\qquad 0 ≤ r < 10↑n.\eqno (2)$$
Now if we apply Method (2a) to the fraction $(q
+ 1)/w$, we will obtain the digits of $u$ from left to right,
in $n$ steps, since
$$\left\lfloor 10↑n\;{q + 1\over w}\right\rfloor
 = \left\lfloor u + {10↑n - r\over w}\right\rfloor= u.\eqno (3)$$
(This idea is due to P. A. Samet, {\sl Software---Practice
and Experience \bf 1} (1971), 93--96.)

Here is the corresponding \MIX\ program:
$$\vcenter{\mixthree{\!
⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
⊗LDA⊗U\cr
⊗LDX⊗=$10↑n$=⊗$\rAX ← wu + 10↑n$.\cr
⊗DIV⊗=$10↑n$=⊗$\rA ← q + 1$, $\rX ← r$.\cr
⊗JOV⊗ERROR⊗Jump if $u ≥ 10↑n$.\cr
⊗ENT1⊗$n$-1⊗Set $j ← n-1$.\cr
2H⊗MUL⊗=10=⊗Now imagine radix point at left, $\rA = x$.\cr
⊗STA⊗ANSWER,1⊗Set $U↓j ← \lfloor 10x\rfloor$.\cr
⊗SLAX⊗5⊗$x ← \{10x\}$.\cr
⊗DEC1⊗1⊗$j ← j - 1$.\cr
⊗J1NN⊗2B⊗Repeat for $n > j ≥ 0$.\quad\blackslug\cr}}\eqno (4)$$
This slightly longer routine requires $16n
+ 19$ cycles, so it is a little faster than program (1) if $n = M ≥
8$; when leading zeros are present, (1) will be faster.

Program (4) as it stands cannot be used to convert
integers $u ≥ 10↑m$ when $10↑m < w < 10↑{m+1}$, since we would
need to take $n = m + 1$. In this case we can obtain the leading
digit of $u$ by computing $\lfloor u/10↑m\rfloor $; then $u
\mod 10↑m$ can be converted as above with $n = m$.

The fact that the answer digits are obtained from
left to right may be an advantage in some applications (e.g.,
when typing out the answer one digit at a time). Thus we see
that a fractional method can be used for conversion of integers,
although the use of inexact division makes a little bit of numerical
analysis necessary.

A modification of Method (1a) can be used to avoid
division by 10, by replacing it with two multiplications. It
is worth mentioning this modification here, because radix conversion
is often done by small ``satellite'' computers that have no
division capability. If we let $x$ be an approximation to ${1\over
10}$, so that ${1\over 10} < x < {1\over 10} + 1/w$, it
is easy to prove (see exercise 7) that $\lfloor ux\rfloor =
\lfloor u/10\rfloor$ or $\lfloor u/10\rfloor + 1$, so long as
$0 ≤ u < w$. Therefore, if we compute $u - 10\lfloor ux\rfloor
$, we will be able to determine the value of $\lfloor u/10\rfloor$:
$$\lfloor u/10\rfloor = \left\{\vcenter{\halign{$\lft{#,}$\qquad
⊗if $u-10\lfloor ux\rfloor#$\cr
\lfloor ux\rfloor⊗≥0;\cr
\lfloor ux\rfloor-1⊗<0.\cr}}\right.\eqno(5)$$
This procedure simultaneously determines $u\mod
10$. A \MIX\ program for conversion using this idea appears in
exercise 8; it requires about 33 cycles per digit.
%folio 403 galley 2 (C) Addison-Wesley 1978	*
The procedure represented by (5) can be used effectively even
if the computer has no built-in multiplication instruction,
since multiplication by 10 consists of two shifts and one addition
($10 = 2↑3 + 2$). Even the task of multiplication by ${1\over 10}$ can
be done by judiciously combining a few shifting and adding operations,
as explained in exercise 9.

Another way to convert from binary to decimal is to use Method (1b),
but to do this we need to simulate doubling in a {\sl decimal}
number system. This idea is generally most suitable for incorporation
into computer hardware; however, it is possible to program the
doubling process for decimal numbers, using binary addition,
binary shifting, and binary extraction (``logical \.{AND}'' on each bit in the
register), as shown in Table 1.

\yyskip{\tablehead{Table 1}
\vskip 3pt plus 2pt minus 1pt
\ctrline{\hbox expand 6pt{DOUBLING A BINARY-CODED DECIMAL NUMBER}}
\vskip 6pt plus 2pt minus 1pt
\ninepoint
\tabskip 0pt plus 100pt
\halign to size{\rt{#} \tabskip 0pt
⊗\lft{#}\quad⊗$\ctr{#}$⊗ $\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗
$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗
$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗\quad\rt{#}⊗$\null#\hfill$\tabskip 0pt plus
 100pt\cr
⊗\sl Operation⊗⊗⊗⊗⊗⊗⊗⊗\hskip -100pt plus 100pt \hbox{\sl General form}\!
\hskip -100pt plus 100pt⊗⊗⊗⊗⊗⊗\sl Example\hfill\cr
\noalign{\vskip 2pt}
1.⊗Given⊗⊗u↓1⊗u↓2⊗u↓3⊗u↓4⊗u↓5⊗u↓6⊗u↓7⊗u↓8⊗u↓9⊗
u↓{10}⊗u↓{11}⊗u↓{12}⊗0011 0110 1001⊗= 3\;6\;9\cr
⊗number\cr
2.⊗Add 3 to⊗⊗v↓1⊗v↓2⊗v↓3⊗v↓4⊗v↓5⊗v↓6⊗v↓7⊗v↓8⊗v↓9⊗v↓{10}⊗
v↓{11}⊗v↓{12}⊗0110 1001 1100\cr
⊗each digit\cr
3.⊗Shift left⊗v↓1⊗v↓2⊗v↓3⊗v↓4⊗v↓5⊗v↓6⊗v↓7⊗v↓8⊗v↓9⊗v↓{10}⊗v↓{11}⊗
v↓{12}⊗0⊗0 1101 0011 1000\cr
⊗one\cr
4.⊗Extract low⊗v↓1⊗0⊗0⊗0⊗v↓5⊗0⊗0⊗0⊗v↓9⊗0⊗0⊗0⊗0⊗0 0001 0001
0000\cr
⊗bit\cr
5.⊗Shift right⊗⊗0⊗v↓1⊗0⊗0⊗0⊗v↓5⊗0⊗0⊗0⊗v↓9⊗0⊗0⊗
0000 0100 0100\cr
⊗two\cr
6.⊗Shift right⊗⊗0⊗v↓1⊗v↓1⊗0⊗0⊗v↓5⊗v↓5⊗0⊗0⊗v↓9⊗v↓9⊗0⊗
0000 0110 0110\cr
⊗one and add\cr
7.⊗Add result⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗\ast⊗0
⊗0 1101 1001 1110\cr
⊗of step 3\cr
8.⊗Subtract 6⊗y↓1⊗y↓2⊗y↓3⊗y↓4⊗y↓5⊗y↓6⊗y↓7⊗y↓8⊗y↓9⊗y↓{10}⊗y↓{11}⊗
y↓{12}⊗0⊗0 0111 0011 1000⊗= 7\;3\;8\cr
⊗from each\cr}}

\yyskip This method changes each individual digit $d$
into $\biglp (d + 3) \times 2 + 0) - 6 = 2d$ when $0 ≤ d ≤ 4$,
and into $\biglp (d + 3) \times 2 + 6\bigrp - 6 = (2d - 10)
+ 2↑4$ when $5 ≤ d ≤ q$; and that is just what is needed to
double decimal numbers encoded with 4 bits per digit.

Another related idea is to keep a table
of the powers of two in decimal form, and to add the appropriate
powers together by simulating decimal addition. A survey of
such bit-manipulation techniques appears in Section 7.1.

Finally, even Method (2b) can be used for the conversion of
binary integers to decimal integers. We can find $q$ as in
(2), and then we can simulate the decimal division of $q + 1$
by $w$, using a ``halving'' process (exercise 10) that is similar
to the doubling process just described, retaining only the
first $n$ digits to the right of the radix point in the answer.
In this situation, Method (2b) does not seem to offer advantages
over the other three methods already discussed, but we have
confirmed the remark made earlier that at least four distinct
methods are available for converting integers from one radix
to another.

\yskip Now let us consider decimal-to-binary conversion (so that $b=10$, $B=2$).
Method (1a) simulates a decimal division by 2; this is feasible
(see exercise 10), but it is primarily suitable for incorporation
in hardware instead of programs.

Method (1b) is the most practical method
for decimal-to-binary conversion in the great majority of cases.
Here it is in \MIX\ code, assuming that there are at least two
digits in the number $(u↓m \ldotsm u↓1u↓0)↓{10}$ being converted:
$$\vcenter{\mixthree{\!
⊗ENT1⊗M-1⊗Set $j ← m - 1$.\cr
⊗LDA⊗INPUT+M⊗Set $U ← u↓m$.\cr
1H⊗MUL⊗=10=\cr
⊗SLAX⊗5\cr
⊗ADD⊗INPUT,1⊗$U ← 10U + u↓j$.\cr
⊗DEC1⊗1\cr
⊗J1NN⊗1B⊗Repeat for $m > j ≥ 0$.\quad\blackslug\cr}}\eqno (6)$$
Note again that adding and shifting may be
substituted for multiplication by 10.

A trickier but perhaps faster method, which uses about $\lg m$
multiplications, extractions, and additions instead of $m$ multiplications
and additions, is described in exercise 19.

For the conversion of decimal fractions $(0.u↓{-1}u↓{-2} \ldotsm
u↓{-m})↓{10}$, we can use Method (2b), or, more commonly, we
can convert the integer $(u↓{-1}u↓{-2} \ldotsm u↓{-m})↓{10}$
by Method (1b) and then divide by $10↑m$.

\subsectionbegin{C. Hand calculation} It is occasionally
necessary for computer programmers to convert numbers
by hand, and since this is a subject not yet taught in elementary
schools, it may be worth while to examine it briefly here. There
are very simple pencil-and-paper methods for converting between
decimal and octal notations, and these methods are easily learned,
so they ought to be more widely known.

\yyskip\noindent {\sl Converting octal integers to decimal.}\xskip
The simplest conversion is from octal to decimal; this technique
was apparently first published by Walter Soden, {\sl Math.\ Comp.\
\bf 7} (1953), 273--274. To do the conversion, write down the
given octal number; then at the $k$th step, double the $k$ leading
digits using decimal arithmetic, and subtract this from the
$k + 1$ leading digits using decimal arithmetic. The process
terminates in $n - 1$ steps if the given number has $n$ digits.
It is a good idea to insert a radix point to show which digits
are being doubled, as shown in the following example, in order
to prevent embarrassing mistakes.

\thbegin Example 1. Convert $(5325121)↓8$ to decimal.
$$\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 5pt{\hfill.\hfill}}
\def\\{\lower 2.5pt\vbox to 12pt{}}
\def\¬{$-$ \\}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{\hbox to 100pt{\hfill#}⊗\hbox to 100pt{#\hfill}⊗\hbox to 148pt
{#\hfill}\cr
\\⊗5\dot3\92\95\91\92\91\cr
\¬⊗1\90\cr
\bar⊗\vbox{\hrule width 15pt}\cr
\\⊗4\93\dot2\95\91\92\91\cr
\¬⊗\9\98\96\cr
\bar⊗\vbox{\hrule width 25pt}\cr
\\⊗3\94\96\dot5\91\92\91\cr
\¬⊗\9\96\99\92\cr
\bar⊗\vbox{\hrule width 35pt}\cr
\\⊗2\97\97\93\dot1\92\91\cr
\¬⊗\9\95\95\94\96\cr
\bar⊗\vbox{\hrule width 45pt}\cr
\\⊗2\92\91\98\95\dot2\91\cr
\¬⊗\9\94\94\93\97\90\cr
\bar⊗\vbox{\hrule width 55pt}\cr
\\⊗1\97\97\94\98\92\dot1\cr
\¬⊗\9\93\95\94\99\96\94\cr
\bar⊗\vbox{\hrule width 65pt}\cr
\\⊗1\94\91\99\98\95\97⊗\sl Answer: $(14198757)↓{10}$.\cr}}$$

A reasonably good check on the computations may
be had by ``casting out nines'': The sum of the digits of the
decimal number must equal the alternating sum and difference
of the digits of the octal number, with the rightmost digit
of the latter given a plus sign, except for a multiple of nine.
In the above example, we have $1 + 4 + 1 + 9 + 8 + 5 + 7 = 35$,
and $1 - 2 + 1 - 5 + 2 - 3 + 5 = -1$; the difference is 36
(a multiple of 9). If this test fails, it can be applied to
the $k + 1$ leading digits after the $k$th step, and the error
can be located using a ``binary search'' procedure; i.e., start
by checking the middle result, then use the same procedure on
the first or second half of the calculation, depending on whether
the middle result is incorrect or correct.

The ``casting-out-nines'' process is only about 89
percent reliable, because there is one chance in nine that two {\sl random}
integers will differ by a multiple of nine. An even better check
is to convert the answer back to octal by using an inverse method,
which we shall now consider.

\yyskip\noindent{\sl Converting decimal integers to octal.}\xskip
A similar procedure can be used for the opposite conversion:
Write down the given decimal number; then at the $k$th step, double
the $k$ leading digits using {\sl octal} arithmetic, and {\sl
add} these to the $k + 1$ leading digits using {\sl octal} arithmetic.
The process terminates in $n - 1$ steps if the given number
has $n$ digits.\xskip (See example 2 on the following page.)

\topinsert{
\hbox{{\bf Example 2.}\xskip Convert $(1419857)↓{10}$ to octal.}
\vskip 12pt plus 3pt minus 9pt
\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 5pt{\hfill.\hfill}}
\def\\{\lower 2.5pt\vbox to 12pt{}}
\def\¬{$+$ \\}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{\hbox to 100pt{\hfill#}⊗\hbox to 100pt{#\hfill}⊗\hbox to 148pt
{#\hfill}\cr
\\⊗1\dot4\91\99\98\95\97\cr
\¬⊗\9\92\cr
\bar⊗\vbox{\hrule width 15pt}\cr
\\⊗1\96\dot1\99\98\95\97\cr
\¬⊗\9\93\94\cr
\bar⊗\vbox{\hrule width 25pt}\cr
\\⊗2\91\95\dot9\98\95\97\cr
\¬⊗\9\94\93\92\cr
\bar⊗\vbox{\hrule width 35pt}\cr
\\⊗2\96\91\93\dot8\95\97\cr
\¬⊗\9\95\94\92\96\cr
\bar⊗\vbox{\hrule width 45pt}\cr
\\⊗3\93\95\96\96\dot5\97⊗\vbox to 0pt{\baselineskip12pt\vskip 0pt minus 100pt
\jpar 1000\hbox to 148pt{(Note that the nonoctal digits 8 and 9 enter into this
octal computation.) The answer can be checked as discussed above. This method
was published by Charles P. Rozier, {\sl IEEE Trans.\ \bf CE--11} (1962),
708--709.}}\cr
\¬⊗\9\96\97\93\95\94\cr
\bar⊗\vbox{\hrule width 55pt}\cr
\\⊗4\92\95\92\94\91\dot7\cr
\¬⊗1\90\95\92\95\90\92\cr
\bar⊗\vbox{\hrule width 65pt}\cr
\\⊗5\93\92\95\91\92\91⊗\sl Answer: $(5325121)↓8$.\cr}}}

The two procedures just given are
essentially Method (1b) of the general radix-conversion procedures.
Doubling and subtracting in decimal notation is like multiplying
by $10 - 2 = 8$; doubling and adding in octal notation is like
multiplying by $8 + 2 = 10$. There is a similar method for hexadecimal/decimal
conversions, but it is a little more difficult since it involves
multiplication by 6 instead of by 2.

To keep these two methods straight in our minds, it is not hard
to remember that we must subtract to go from octal to decimal, since the decimal
representation of a number is smaller; similarly we must add to go from
decimal to octal. The computations are performed using the radix of the
{\sl answer}, not the radix of the given number, otherwise we couldn't get
the desired answer.
%folio 407 galley 3 (C) Addison-Wesley 1978	*
\yyskip\noindent{\sl Converting fractions.\xskip} No equally
fast method of converting fractions manually is known; the best
way seems to be Method (2a), with doubling and adding or subtracting
to simplify the multiplications by 10 or by 8. In this case,
we reverse the addition-subtraction criterion, adding when we
convert to decimal and subtracting when we convert to octal;
we also use the radix of the given input number, {\sl not} the
radix of the answer, in this computation (see Examples 3 and
4). The process is about twice as hard as the above method for
integers.

\yyskip
\hbox to size{\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 5pt{\hfill.\hfill}}
\def\\{\lower 2.5pt\vbox to 12pt{}}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{#\hfill\cr
\\\bf Example 3.\xskip Convert $(.14159)↓{10}$\cr
\\to octal.\cr
\noalign{\vskip 2pt}
\\\dot1\94\91\95\99\cr
\\\9\9\92\98\93\91\98$-$\cr
\bar\vbox{\moveright5pt\vbox{\hrule width 55pt}}\cr
\\\91\dot1\93\92\97\92\cr
\\\9\9\9\9\92\96\95\94\94$-$\cr
\bar\vbox{\moveright15pt\vbox{\hrule width 55pt}}\cr
\\\9\9\91\dot0\96\91\97\96\cr
\\\9\9\9\9\9\9\91\92\93\95\92$-$\cr
\bar\vbox{\moveright25pt\vbox{\hrule width 55pt}}\cr
\\\9\9\9\9\90\dot4\99\94\90\98\cr
\\\9\9\9\9\9\9\9\9\99\98\98\91\96$-$\cr
\bar\vbox{\moveright35pt\vbox{\hrule width 55pt}}\cr
\\\9\9\9\9\9\9\93\dot9\95\92\94\96\cr
\\\9\9\9\9\9\9\9\9\91\99\90\95\92\98$-$\cr
\bar\vbox{\moveright45pt\vbox{\hrule width 55pt}}\cr
\\\9\9\9\9\9\9\9\9\97\dot6\92\91\91\92\cr
\\\9\9\9\9\9\9\9\9\9\9\91\92\94\92\92\94$-$\cr
\bar\vbox{\moveright55pt\vbox{\hrule width 55pt}}\cr
\\\9\9\9\9\9\9\9\9\9\9\94\dot9\96\98\99\96\cr
\noalign{\vskip 3pt}
\sl Answer: $(.110374\ldotsm)↓8.$\cr}}\hfill
\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 5pt{\hfill.\hfill}}
\def\\{\lower 2.5pt\vbox to 12pt{}}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{#\hfill\cr
\\\bf Example 4.\xskip Convert $(.110374)↓8$\cr
\\to decimal.\cr
\noalign{\vskip 2pt}
\\\dot1\91\90\93\97\94\cr
\\\9\9\92\92\90\97\97\90$+$\cr
\bar\vbox{\moveright5pt\vbox{\hrule width 65pt}}\cr
\\\91\dot3\92\94\97\93\90\cr
\\\9\9\9\9\96\95\91\96\96\90$+$\cr
\bar\vbox{\moveright15pt\vbox{\hrule width 65pt}}\cr
\\\9\9\94\dot1\92\91\91\96\90\cr
\\\9\9\9\9\9\9\92\94\92\93\94\90$+$\cr
\bar\vbox{\moveright25pt\vbox{\hrule width 65pt}}\cr
\\\9\9\9\9\91\dot4\95\94\91\94\90\cr
\\\9\9\9\9\9\9\91\91\93\90\93\90\90$+$\cr
\bar\vbox{\moveright35pt\vbox{\hrule width 65pt}}\cr
\\\9\9\9\9\9\9\95\dot6\97\91\97\90\90\cr
\\\9\9\9\9\9\9\9\9\91\95\96\93\96\90\90$+$\cr
\bar\vbox{\moveright45pt\vbox{\hrule width 65pt}}\cr
\\\9\9\9\9\9\9\9\9\98\dot5\90\92\96\90\90\cr
\\\9\9\9\9\9\9\9\9\9\9\91\92\90\95\94\90\90$+$\cr
\bar\vbox{\moveright55pt\vbox{\hrule width 65pt}}\cr
\\\9\9\9\9\9\9\9\9\9\9\96\dot2\93\93\94\90\90\cr
\noalign{\vskip 3pt}
\sl Answer: $(.141586\ldotsm)↓{10}$\cr}}}

\subsectionbegin{D. Floating-point
conversion} When floating-point values are to be converted,
it is necessary to deal with both the exponent and the fraction
parts simultaneously, since conversion of the exponent will
affect the fraction part. Given the number $f \cdot 2↑e$ to
be converted to decimal, we may express $2↑e$ in the form $F
\cdot 10↑E$ (usually by means of auxiliary tables), and then
convert $Ff$ to decimal. Alternatively, we can multiply $e$
by $\log↓{10} 2$ and round this to the nearest integer $E$; then
divide $f \cdot 2↑e$ by $10↑E$ and convert the result. Conversely,
given the number $F \cdot 10↑E$ to be converted to binary, we
may convert $F$ and then multiply it by the floating-point number
$10↑E$ (again by using auxiliary tables). Obvious techniques
can be used to reduce the maximum size of the auxiliary tables
by using several multiplications and/or divisions, although
this can cause rounding errors to propagate.

\subsectionbegin{E. Multiple-precision conversion}
When converting multiprecision numbers, it is most convenient
to start by converting blocks of digits, which can be handled
by single-precision techniques, and then to combine these blocks by using simple
multiple-precision techniques. For example, suppose that $10↑n$
is the highest power of 10 less than the computer word size.
Then

\yskip\textindent{a)}To convert a multiple-precision {\sl integer} from
binary to decimal, divide it repeatedly by $10↑n$ $\biglp$thus converting
from binary to radix $10↑n$ by Method (1a)$\bigrp$. Single-precision
operations will give the $n$ decimal digits for each place of
the radix-$10↑n$ representation.

\textindent{b)}To convert a multiple-precision {\sl fraction} from binary
to decimal, proceed similarly, multiplying by $10↑n$ $\biglp$i.e.,
using Method (2a) with $B = 10↑n\bigrp$.

\textindent{c)}To convert a multiple-precision integer from
decimal to binary, convert blocks of $n$ digits first; then
convert from radix $10↑n$ to binary by using Method (1b).

\textindent{d)}Finally, a multiple-precision fraction may be converted from
decimal to binary by a technique similar to (c), using Method
(2b).

\subsectionbegin{F. History and Bibliography} Radix-conversion
techniques implicitly originated in ancient problems
dealing with weights, measures, and currencies, when a mixed-radix
system was generally involved. Auxiliary tables were usually
used as an aid to conversion. During the seventeenth century
when sexagesimal fractions were being supplanted by decimal
fractions, it was necessary to convert between the two systems
in order to use existing books of tables; a systematic method
to transform fractions from radix 60 to radix 10 and vice versa
was given in the 1667 edition of William Oughtred's {\sl Clavis
Mathematic\ae}, Chapter 6, Section 18.\xskip (This material was
not present in the original 1631 edition of Oughtred's book.)\xskip
Conversion rules had been given already by al-Kash\A\i\
of Persia in his {\sl Key to Arithmetic} (c. 1414), where Methods
(1a), (1b), and (2a) are clearly explained [{\sl Istoriko-Mat.\
Issled.\ \bf 7} (1954), 126--135], but his work was unknown in
Europe. The 18th century American mathematician Hugh Jones used
the words ``octavation'' and ``decimation'' to describe octal/decimal
conversions, but his methods were not as clever as his terminology.
A. M. Legendre [{\sl Th\'eorie des nombres} (Paris, 1798),
229] noted that positive integers may be conveniently converted
to binary form if they are repeatedly divided by 64.

In 1946, H. H. Goldstine and J. von Neumann gave prominent consideration
to radix conversion in their classic memoir, ``Planning and
coding problems for an electronic computing instrument,'' because
it was necessary to justify the use of binary arithmetic; see
John von Neumann, {\sl Collected Works \bf 5} (New York: Macmillan,
1963), 127--142. Another early discussion of radix conversion
on binary computers was published by F. Koons and S. Lubkin,
{\sl Math.\ Comp.\ \bf 3} (1949), 427--431, who suggested a rather unusual
method. The first discussion of floating-point
conversion was given somewhat later by F. L. Bauer and K. Samelson
[{\sl Zeit.\ f\"ur angewandte Math.\ und Physik \bf 4} (1953),
312--316].

The following articles may be useful for further reference:
A note by G. T. Lake [{\sl CACM \bf 5} (1962), 468--469] mentions
some hardware techniques for conversion and gives clear examples.
A. H. Stroud and D. Secrest [{\sl Comp.\ J. \bf 6} (1963), 62--66]
have discussed conversion of multiple-precision floating-point
numbers. The conversion of {\sl unnormalized} floating-point
numbers, preserving the amount of ``significance'' implied by
the representation, has been discussed by H. Kanner [{\sl JACM
\bf 12} (1965), 242--246] and by N. Metropolis and R. L. Ashenhurst
[{\sl Math.\ Comp.\ \bf 19} (1965), 435--441]. See also K. Sikdar,
{\sl Sankhy\=a} series B, {\bf 30} (1968), 315--334, and the references
he cites.

\exbegin{EXERCISES}

\trexno 1. [25] Generalize
Method (1b) so that it works with arbitrary mixed-radix notations, converting
$$a↓mb↓{m-1} \ldotsm b↓1b↓0 + \cdots + a↓1b↓0 + a↓0\hskip10pt minus10pt
\hbox{into}\hskip10pt minus10pt
A↓MB↓{M-1} \ldotsm B↓1B↓0 + \cdots + A↓1B↓0 + A↓0,$$
where $0 ≤ a↓j < b↓j$, $0 ≤ A↓J < B↓J$ for $0 ≤ j
< m$, $0 ≤ J < M$.

Give an example of your generalization by manually
converting the quantity ``3 days, 9 hours, 12 minutes, and 37
seconds'' into long tons, hundredweights, stones, pounds, and
ounces.\xskip (Let one second equal one ounce. The British system
of weights has 1 stone = 14 pounds, 1 hundredweight = 8 stone,
1 long ton = 20 hundredweight.)\xskip In other words, let $b↓0 = 60$,
$b↓1 = 60$, $b↓2 = 24$, $m = 3$, $B↓0 = 16$, $B↓1 = 14$, $B↓2 = 8$, $B↓3
= 20$, $M = 4$; the problem is to find $A↓4$, $\ldotss$, $A↓0$ in
the proper ranges such that $3b↓2b↓1b↓0 + 2b↓1b↓0 + 12b↓0 +
37 = A↓4B↓3B↓2B↓1B↓0 + A↓3B↓2B↓1B↓0 + A↓2B↓1B↓0 + A↓1B↓0 + A↓0$,
using a systematic method that generalizes Method (1b).\xskip (All
arithmetic is to be done in a mixed-radix system.)

\exno 2. [25] Generalize Method (1a) so that it works with mixed-radix
notations, as in exercise 1, and give an example of your generalization
by manually solving the same conversion problem stated in exercise
1.

\trexno 3. [25] (D. Taranto.)\xskip When fractions
are being converted, there is in general no obvious way to decide
how many digits to give in the answer. Design a simple generalization
of Method (2a) that, given two positive radix-$b$ fractions
$u$ and $ε$ between 0 and 1, converts $u$ to a rounded radix-$B$
equivalent $U$ that has just enough places $M$ to the right of the radix point
to ensure that $|U - u| < ε$.\xskip
$\biglp$In particular if $u$ is a multiple of $b↑{-m}$ and
$ε=b↑{-m}/2$, the value of $U$ will have just enough digits so that $u$ can be
recomputed exactly, given $U$ and $m$. Note that $M$ might be zero; for example,
if $ε≤{1\over2}$ and $u>1-ε$, the proper answer is $U=1$.$\bigrp$

\exno 4. [M21] (a) Prove that every real number having a
terminating {\sl binary} representation also has a terminating
{\sl decimal} representation.\xskip (b) Find a simple condition on
the positive integers $b$ and $B$ that is satisfied if and
only if every real number that has a terminating radix-$b$
representation also has a terminating radix-$B$ representation.

\exno 5. [M20] Show that program (4) would work also if the
instruction ``\.{LDX =$10↑n$=}'' were replaced by ``\.{LDX =$c$=}'' for
certain other constants $c$.

\exno 6. [30] Discuss using Methods (1a), (1b), (2a), and (2b)
when $b$ or $B$ is $-2$.

\exno 7. [M18] Given that $0 < α ≤ x ≤ α + 1/w$ and $0 ≤ u ≤
w$, prove that $\lfloor ux\rfloor$ is equal to either $\lfloor αu\rfloor$ or
$\lfloor αu\rfloor + 1$. Furthermore $\lfloor ux\rfloor = \lfloor αu\rfloor$
exactly, if $u < αw$ and $α↑{-1}$ is an integer.

\exno 8. [24] Write a \MIX\ program analogous to (1) that uses
(5) and includes no division instructions.

\exno 9. [M27] Let $u$ be an integer, $0 ≤ u < 2↑{34}$. Assume
that the following sequence of operations (equivalent to addition
and binary ``shift-right'' instructions) is performed:
$$\baselineskip13pt
\eqalign{v⊗←\lfloor\textstyle{1\over2}u\rfloor,\cr
v⊗←v+\lfloor2↑{-8}v\rfloor,\cr}
\qquad\eqalign{v⊗←v+\textstyle\lfloor{1\over2}v\rfloor,\cr
v⊗←v+\lfloor2↑{-16}v\rfloor,\cr}
\qquad\eqalign{v⊗←v+\lfloor2↑{-4}v\rfloor,\cr
v⊗←\lfloor\textstyle{1\over8}v\rfloor.\cr}$$
Prove that $v = \lfloor u/10\rfloor$ or $\lfloor u/10\rfloor
- 1$.

\exno 10. [22] The text shows how a binary-coded decimal number
can be doubled by using various shifting, extracting, and addition
operations on a binary computer. Give an analogous method that
computes {\sl half\/} of a binary-coded decimal number (throwing
away the remainder if the number is odd).
%folio 411 galley 4a (C) Addison-Wesley 1978	*
\exno 11. [16] Convert $(57721)↓8$ to decimal.

\trexno 12. [22] Invent a rapid pencil-and-paper method for converting
integers from ternary notation to decimal, and illustrate your
method by converting $(1212011210210)↓3$ into decimal. How would
you go from decimal to ternary?

\trexno 13. [25] Assume that locations $\.U + 1$, $\.U + 2$, $\ldotss$,
$\.U + m$ contain a multiple-precision fraction $(.u↓{-1}u↓{-2}
\ldotsm u↓{-m})↓b$, where $b$ is the word size of \MIX. Write
a \MIX\ routine that converts this fraction to decimal notation,
truncating it to 180 decimal digits. The answer should be printed
on two lines, with the digits grouped into 20 blocks of nine
each separated by blanks.\xskip (Use the \.{CHAR} instruction.)

\trexno 14. [M27] (A. Sch\"onhage.)\xskip The text's method of
converting multiple-precision integers requires an execution
time of order $n↑2$ to convert an $n$-place integer, when $n$
is large. Show that it is possible to convert $n$-digit decimal
integers into binary notation in $O\biglp M(n)\log n\bigrp$
steps, where $M(n)$ is an upper bound on the number of steps
needed to multiply $n$-bit binary numbers that satisfies the ``smoothness
condition'' $M(2n)≥2M(n)$.

\exno 15. [M50] Can the upper bound on the time to convert large integers,
given in exercise 14, be substantially lowered?\xskip (Cf.\ exercise 4.3.3-12.)

\exno 16. [41] Construct a fast linear iterative array for radix conversion
from decimal to binary (cf.\ Section 4.3.3).

\exno 17. [M40] Design ``ideal'' floating-point conversion subroutines, taking
$p$-digit decimal numbers into $P$-digit binary numbers and vice versa, in
both cases producing a true rounded result in the sense of Section 4.2.2.

\exno 18. [HM39] (David W. Matula.)\xskip Let $\hbox{round}
↓b(u,p)$ be the function of $b$, $u$, and $p$ that represents the
best $p$-digit base $b$ floating-point approximation to $u$,
in the sense of Section 4.2.2. Under the assumption that $\log↓B
b$ is irrational and that the range of exponents is unlimited,
prove that
$$u=\hbox{round}↓b\biglp\hbox{round}↓B(u,P),p\bigrp$$
holds for all $p$-digit base $b$ floating-point numbers
$u$ if and only if $B↑{p-1} ≥ b↑p$.\xskip (In other words, an ``ideal''
input conversion of $u$ into an independent base $B$, followed
by an ``ideal'' output conversion of this result, will always
yield $u$ again if and only if the intermediate precision $P$
is suitably large, as specified by the formula above.)

\exno 19. [M23] Let the decimal number $u = (u↓7 \ldotsm u↓1u↓0)↓{10}$
be represented as the binary-coded decimal number $U = (u↓7
\ldotsm u↓1u↓0)↓{16}$. Find appropriate constants $c↓i$ and masks
$m↓i$ so that the operation $U ← U - c↓i(U ∧ m↓i)$, repeated
for $i = 1$, 2, 3, will convert $U$ to the binary representation
of $u$, where ``$∧$'' denotes extraction (i.e., ``logical \.{AND}''
on individual bits).

\vfill\eject